#include <vector>


class Solution {
public:
    int largest1BorderedSquare(std::vector<std::vector<int>>& grid) {
        vuild(grid);
        int n = grid.size();
        int m = grid[0].size();
        if (sum(grid,0,0,n-1,m-1) == 0)
            return 0;
        int ans = 1;
        for (int i=0;i<n;i++)
        {
            for (int j=0;j<m;j++)
            {
               for (int c= i + ans,d = j +ans,k= ans+1;c<n&&d<m;c++,d++,k++)
               {
                   if (sum(grid,i,j,c,d) - sum(grid,i+1,j+1,c-1,d-1)==(k-1)<< 2)
                   {
                       ans = k;
                   }
               }
                
            }
        }
        return ans*ans;
    }
    void vuild(std::vector<std::vector<int>>& grid)
    {
        int n = grid.size();
        int m = grid[0].size();
        for (int i = 0; i <n; i++)
        {
            for (int j=0;j<m;j++)
            {
                grid[i][j]+=get(i,j-1,grid)+get(i-1,j,grid)-get(i-1,j-1,grid);
            }
        }
    }
    int get(int i,int j,std::vector<std::vector<int>>& g)
    {
        return (i<0 || j<0)?0:g[i][j];
    }
    int sum(std::vector<std::vector<int>>& g,int a,int b,int c,int d)
    {
        return a>c ? 0:(g[c][d] - get(c,b-1,g)-get(a-1,d,g)+get(a-1,b-1,g));
    }
};